package com.likou;

import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * Author: 陈桂明
 * Date: 2025/8/29 16:41
 * Description: q76
 */
public class q76 {

    public static void main(String[] args) {
        q76 q76 = new q76();
        String s = "ab", t = "b";
        String s1 = q76.minWindow(s, t);
        System.out.println(s1);
    }

    public String minWindow(String s, String t) {
        if (t.length() > s.length()) {
            return "";
        }
        if (t.equals("")) {
            return "";
        }
        if (s.equals(t)) {
            return t;
        }
        String ans = "";
        int min = Integer.MAX_VALUE;
        int sLen = s.length();
        int tLen = t.length();
        int left = 0;

        Map<Character, Integer> sMap = new HashMap<>();
        Map<Character, Integer> tMap = new HashMap<>();
        for (int i = 0; i < tLen; i++) {
            sMap.put(s.charAt(i), sMap.getOrDefault(s.charAt(i), 0) + 1);
            tMap.put(t.charAt(i), tMap.getOrDefault(t.charAt(i), 0) + 1);
        }
        if (sMap.keySet().containsAll(tMap.keySet())) {
            int m = 1;
            for (Character key : tMap.keySet()) {
                if (sMap.get(key) < tMap.get(key)) {
                    m = 0;
                    break;
                }
            }
            if (m == 1) {
                return s.substring(left, tLen);
            }

        }

        // 开始滑动
        int right = tLen;
        for (; right < sLen; right++) {
            char c = s.charAt(right);
            sMap.put(c, sMap.getOrDefault(c, 0) + 1);

            int mark = 1;
            while (mark == 1 && left <= right && sMap.keySet().containsAll(tMap.keySet())) {
                for (Character key : tMap.keySet()) {
                    if (sMap.get(key) < tMap.get(key)) {
                        mark = 0;
                        break;
                    }
                }

                if (mark == 1) {
                    int sum = sMap.values().stream().mapToInt(Integer::intValue)  // 转换为IntStream
                            .sum();
                    if (sum < min) {
                        min = sum;
                        ans = s.substring(left, right + 1);
                    }
                    char c1 = s.charAt(left);
                    left++;
                    if (sMap.get(c1) == 1) {
                        sMap.remove(c1);
                    } else {
                        sMap.put(c1, sMap.get(c1) - 1);
                    }
                }
            }

        }

        return ans;
    }
}
